#pragma once

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include "unionfindset.h"

namespace Matrix
{
    template <class V, class W, W max_w = __INT_MAX__, bool Direction = false>
    class Graph
    {
        typedef Graph<V, W, max_w, Direction> Self;

    public:
        Graph() = default;
        Graph(const V *a, size_t n)
        {
            _vertex.reserve(n);
            for (size_t i = 0; i < n; i++)
            {
                _vertex.push_back(a[i]);
                _index[a[i]] = i;
            }
            _matrix.resize(n);
            for (size_t i = 0; i < n; i++)
            {
                _matrix[i].resize(n, max_w);
            }
        }
        size_t GetVertexIndex(const V &v)
        {
            auto it = _index.find(v);
            if (it != _index.end())
            {
                return it->second;
            }
            else
            {
                // assert()
                // throw invalid_argument("顶点不存在");
                return -1;
            }
        }
        void _AddEdge(size_t srci, size_t dsti, const W &w)
        {
            _matrix[srci][dsti] = w;
            // 无向图
            if (Direction == false)
            {
                _matrix[dsti][srci] = w;
            }
        }
        void AddEdge(const V &v1, const V &v2, const W &w)
        {
            size_t srci = GetVertexIndex(v1);
            size_t dsti = GetVertexIndex(v2);
            _matrix[srci][dsti] = w;
            _AddEdge(srci, dsti, w);
        }
        void Print()
        {
            // 打印映射关系
            for (int i = 0; i < _vertex.size(); i++)
            {
                std::cout << "[" << _vertex[i] << "]->" << _index[_vertex[i]] << std::endl;
            }
            std::cout << std::endl;

            // 打印上表头
            std::cout << "  ";
            for (size_t i = 0; i < _vertex.size(); i++)
            {
                std::cout << i << " ";
            }
            std::cout << std::endl;
            // 打印矩阵
            for (int i = 0; i < _matrix.size(); i++)
            { // 打印左表头
                std::cout << i << " ";
                for (size_t j = 0; j < _matrix[i].size(); j++)
                {
                    if (_matrix[i][j] == __INT_MAX__)
                    {
                        std::cout << "* ";
                    }
                    else
                        std::cout << _matrix[i][j] << " ";
                }
                std::cout << std::endl;
            }
            std::cout << std::endl;
        }

        void BFS(const V &src)
        {
            size_t srci = GetVertexIndex(src);
            std::vector<bool> vist;
            vist.resize(_vertex.size(), false);

            std::queue<int> q;
            q.push(srci);
            vist[srci] = true;
            size_t levelsize = 1;
            while (!q.empty())
            {
                for (size_t i = 0; i < levelsize; i++)
                {
                    int front = q.front();
                    q.pop();
                    std::cout << "[" << front << "]" << _vertex[front] << "->";
                    for (size_t j = 0; j < _vertex.size(); j++)
                    {
                        if (!vist[j] && _matrix[front][j] != __INT_MAX__)
                        {
                            vist[j] = true;
                            q.push(j);
                        }
                    }
                }
                std::cout << std::endl;
                levelsize = q.size();
            }
        }

        void DFS(const V &src, std::vector<bool> &vist)
        {
            size_t srci = GetVertexIndex(src);
            std::cout << "[" << srci << "]" << _vertex[srci];
            vist[srci] = true;
            for (size_t j = 0; j < _vertex.size(); j++)
            {
                if (!vist[j] && _matrix[srci][j] != __INT_MAX__)
                {
                    DFS(_vertex[j], vist);
                }
            }
        }

        struct Edge
        {
            size_t _srci;
            size_t _dsti;
            W _w;

            Edge(size_t srci, size_t dsti, const W &w)
                : _srci(srci), _dsti(dsti), _w(w)
            {
            }

            bool operator>(const Edge &e) const
            {
                return _w > e._w;
            }
        };

        W Kruskal(Self &mintree)
        {
            size_t n = _vertex.size();
            mintree._index = _index;
            mintree._vertex = _vertex;
            mintree._matrix.resize(n);
            for (int i = 0; i < n; i++)
            {
                mintree._matrix[i].resize(n, max_w);
            }

            std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> minqueue;
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    if (i < j && _matrix[i][j] != max_w)
                    {
                        minqueue.push(Edge(i, j, _matrix[i][j]));
                    }
                }
            }

            // 选出最小的n-1条边
            size_t size = 0;
            W totalw = W();

            UnionFindSet<int> ufs(n);

            while (!minqueue.empty())
            {
                Edge mineg = minqueue.top();
                minqueue.pop();
                if (!ufs.IsSet(mineg._srci, mineg._dsti))
                {
                    // 说明不构成环
                    std::cout << _vertex[mineg._srci] << "->" << _vertex[mineg._dsti] << ":" << mineg._w << std::endl;
                    mintree._AddEdge(mineg._srci, mineg._dsti, mineg._w);
                    ufs.Union(mineg._srci, mineg._dsti);
                    ++size;
                    totalw += mineg._w;
                }
                else
                {
                    // 构成环
                    std::cout << "构成环：" << std::endl;
                    std::cout << _vertex[mineg._srci] << "->" << _vertex[mineg._dsti] << ":" << mineg._w << std::endl;
                }
            }

            if (size == n - 1)
            {
                return totalw;
            }
            else
            {
                return W();
            }
        }

        W Prim(Self &mintree, const W &src)
        {
            size_t srci = GetVertexIndex(src);
            size_t n = _vertex.size();

            mintree._index = _index;
            mintree._vertex = _vertex;
            mintree._matrix.resize(n);
            for (int i = 0; i < n; i++)
            {
                mintree._matrix[i].resize(n, max_w);
            }

            std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> minqueue;
            W totalw = W();
            size_t size = 0;
            std::vector<bool> X(n, false);
            std::vector<bool> Y(n, true);
            X[srci] = true;
            Y[srci] = false;

            // 把与sric相邻的边都入队列
            for (int i = 0; i < n; i++)
            {
                if (_matrix[srci][i] != max_w)
                {
                    minqueue.push(Edge(srci, i, _matrix[srci][i]));
                }
            }

            while (!minqueue.empty())
            {
                Edge mineg = minqueue.top();
                minqueue.pop();

                // 最小边的目标点也在X集合，则构成环
                if (X[mineg._dsti])
                {
                    std::cout << "构成环:";
                    std::cout << _vertex[mineg._srci] << "->" << _vertex[mineg._dsti] << ":" << mineg._w << std::endl;
                }
                else
                {
                    mintree._AddEdge(mineg._srci, mineg._dsti, mineg._w);
                    std::cout << _vertex[mineg._srci] << "->" << _vertex[mineg._dsti] << ":" << mineg._w << std::endl;
                    X[mineg._dsti] = true;
                    Y[mineg._dsti] = false;
                    totalw += mineg._w;
                    size++;
                    if (size == n - 1)
                    {
                        break;
                    }
                    for (int i = 0; i < n; i++)
                    {
                        if (_matrix[mineg._dsti][i] != max_w && Y[i])
                        {
                            minqueue.push(Edge(mineg._dsti, i, _matrix[mineg._dsti][i]));
                        }
                    }
                }
            }

            if (size == n - 1)
            {
                return totalw;
            }
            else
            {
                return W();
            }
        }

        void PrintShortPath(const V &src, std::vector<W> &dist, std::vector<int> &pPath)
        {
            size_t srci = GetVertexIndex(src);
            size_t n = _vertex.size();

            for (int i = 0; i < n; i++)
            {
                // 找出源点到i顶点的最短路径
                if (i != srci)
                {
                    std::vector<int> path;
                    int parenti = i;
                    while (parenti != srci)
                    {
                        path.push_back(parenti);
                        parenti = pPath[parenti];
                    }
                    path.push_back(srci);
                    reverse(path.begin(), path.end());

                    for (auto index : path)
                    {
                        std::cout << _vertex[index] << "->";
                    }
                    std::cout << dist[i] << std::endl; // 打印最短路径的值
                }
            }
        }

        // 时间复杂度 O(N^2) 空间复杂度O(N)
        void Dijkstra(const V &src, std::vector<W> &dist, std::vector<int> &pPath)
        {
            size_t srci = GetVertexIndex(src);
            size_t n = _vertex.size();
            // 初始化dist和pPath
            dist.resize(n, max_w);
            pPath.resize(n, -1);

            dist[srci] = 0;
            pPath[srci] = srci;

            // 已经确定最短路径的顶点集合
            std::vector<bool> S(n, false);

            // 选出与已确定好的点相连权值最小的那个顶点 并且该选出来的顶点不在集合中
            for (int i = 0; i < n; i++)
            {
                int u = 0;
                W min = max_w;
                for (int j = 0; j < n; j++)
                {
                    if (S[j] == false && dist[j] < min)
                    {
                        u = j;
                        min = dist[j];
                    }
                }
                S[u] = true;

                // 松弛更新u连接顶点v  srci->u + u->v <  srci->v  更新
                for (size_t v = 0; v < n; v++)
                {
                    if (S[v] == false && _matrix[u][v] != max_w && dist[u] + _matrix[u][v] < dist[v])
                    {
                        dist[v] = dist[u] + _matrix[u][v];
                        pPath[v] = u; // 存储该选出来的顶点的上一级父顶点
                    }
                }
            }
        }

        // 时间复杂度 O(N^3)
        bool BellmanFord(const V &src, std::vector<W> &dist, std::vector<int> &pPath)
        {
            size_t srci = GetVertexIndex(src);
            size_t n = _vertex.size();
            // 初始化dist和pPath
            dist.resize(n, max_w); // 记录srci-其他顶点最短路径权值数组
            pPath.resize(n, -1);   // 记录srci-其他顶点最短路径上一级父顶点数组

            dist[srci] = W();

            // 需要不断的更新，防止出现路径和权值更新前后顺序问题导致的结果错误
            for (size_t k = 0; k < n; k++)
            {
                bool update = false; // 观察第二轮是否更新，没有更新的话直接break退出更新
                std::cout << "更新的第" << k + 1 << "轮" << std::endl;
                for (size_t i = 0; i < n; i++)
                {
                    for (size_t j = 0; j < n; j++)
                    {
                        // srci -> i + i ->j
                        if (_matrix[i][j] != max_w && dist[i] + _matrix[i][j] < dist[j]) // dist[i]不能出矩阵中取，因为它的最短路径可能不是直接路径
                        {
                            update = true; // 更新过的标志
                            std::cout << _vertex[i] << "->" << _vertex[j] << ":" << _matrix[i][j] << std::endl;
                            dist[j] = dist[i] + _matrix[i][j];
                            pPath[j] = i;
                        }
                    }
                }

                if (update == false) // 说明没有进入更新
                {
                    break;
                }
            }

            // 还能更新就是带负权回路
            for (size_t i = 0; i < n; ++i)
            {
                for (size_t j = 0; j < n; ++j)
                {
                    // srci -> i + i ->j
                    if (_matrix[i][j] != max_w && dist[i] + _matrix[i][j] < dist[j])
                    {
                        return false;
                    }
                }
            }

            return true;
        }

        void FloydWarshall(std::vector<std::vector<W>> &vvDist, std::vector<std::vector<int>> &vvpPath)
        {
            size_t n = _vertex.size();
            vvDist.resize(n);
            vvpPath.resize(n);

            for (int i = 0; i < n; i++)
            {
                vvDist[i].resize(n, max_w);
                vvpPath[i].resize(n, -1);
            }

            // 先将所有相连的边添加到vvDist中
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    if (_matrix[i][j] != max_w)
                    {
                        vvDist[i][j] = _matrix[i][j];
                        vvpPath[i][j] = i;
                    }

                    if (i == j)
                    {
                        vvDist[i][j] = W();
                    }
                }
            }

            // 最短路径的更新i-> {其他顶点} ->j
            //// k 作为的中间点尝试去更新i->j的路径
            // 动态规划
            for (size_t k = 0; k < n; k++)
            {
                for (size_t i = 0; i < n; i++)
                {
                    for (size_t j = 0; j < n; j++)
                    {
                        if (vvDist[i][k] != max_w && vvDist[k][j] != max_w && vvDist[i][j] > vvDist[i][k] + vvDist[k][j])
                        {
                            vvDist[i][j] = vvDist[i][k] + vvDist[k][j];
                            // 如果k与j相连 vvpPath[k][j]找到的上一层父顶点就是k
                            // 如果不相连，找到的就是vvpPath[k][j]的上一层父顶点
                            vvpPath[i][j] = vvpPath[k][j];
                        }
                    }
                }

                // 打印权值和路径矩阵观察数据
                for (size_t i = 0; i < n; i++)
                {
                    for (size_t j = 0; j < n; j++)
                    {
                        if (vvDist[i][j] == max_w)
                        {
                            printf("%3c", '*');
                        }
                        else
                        {
                            printf("%3d", vvDist[i][j]);
                        }
                    }
                    std::cout << std::endl;
                }
                std::cout << std::endl;

                for (size_t i = 0; i < n; i++)
                {
                    for (size_t j = 0; j < n; j++)
                    {
                        printf("%3d", vvpPath[i][j]);
                    }
                    std::cout << std::endl;
                }
                std::cout << "=================================" << std::endl;
            }
        }

    private:
        // 存储顶点
        std::vector<V>
            _vertex;
        // 存储顶点和下标的映射关系
        std::map<V, int> _index;
        // 邻接矩阵
        std::vector<std::vector<W>> _matrix;
    };
}

namespace Link_Table
{
    template <class W>
    struct Edgs
    {
        size_t _dst;
        W _w;
        Edgs<W> *_next;
        Edgs(size_t dst, const W &w)
            : _dst(dst), _w(w), _next(nullptr)
        {
        }
    };

    template <class V, class W, bool Drection = false>
    class Graph
    {
    public:
        Graph(const V *a, size_t n)
        {
            _vertex.reserve(n);
            for (size_t i = 0; i < n; i++)
            {
                _vertex.push_back(a[i]);
                _index[a[i]] = i;
            }

            _link_table.resize(n, nullptr);
        }
        size_t GetVertexIndex(const V &v)
        {
            auto it = _index.find(v);
            if (it != _index.end())
            {
                return it->second;
            }
            else
            {
                // assert()
                // throw invalid_argument("顶点不存在");
                return -1;
            }
        }
        void AddEdge(const V &v1, const V &v2, const W &w)
        {
            size_t srci = GetVertexIndex(v1);
            size_t dsti = GetVertexIndex(v2);

            Edgs<W> *eg = new Edgs<W>(dsti, w);
            eg->_next = _link_table[srci];
            _link_table[srci] = eg;

            if (Drection == false)
            {
                Edgs<W> *eg = new Edgs<W>(srci, w);
                eg->_next = _link_table[dsti];
                _link_table[dsti] = eg;
            }
        }
        void Print()
        {
            // 打印映射关系
            for (int i = 0; i < _vertex.size(); i++)
            {
                std::cout << "[" << _vertex[i] << "]->" << _index[_vertex[i]] << std::endl;
            }
            std::cout << std::endl;
            // 打印邻接表
            for (int i = 0; i < _link_table.size(); i++)
            {
                std::cout << "[" << i << "]" << _vertex[i] << ":";
                Edgs<W> *cur = _link_table[i];
                while (cur)
                {
                    std::cout << "[" << cur->_dst << "]" << "[" << cur->_w << "]" << _vertex[cur->_dst];
                    std::cout << "->";
                    cur = cur->_next;
                }
                std::cout << "nullptr" << std::endl;
            }
        }

    private:
        // 存储顶点
        std::vector<V>
            _vertex;
        // 存储顶点和下标的映射关系
        std::map<V, int> _index;
        // 邻接表
        std::vector<Edgs<W> *> _link_table;
    };
}